package Atop100.erfen1;

public class Class74 {

//TODO:2023/10/29  官方题解
    class Solution {

        public boolean searchMatrix(int[][] matrix, int target) {
            int rowIndex = binarySearchFirstColumn(matrix, target);
            if (rowIndex < 0) {
                return false;
            }
            return binarySearchRow(matrix[rowIndex], target);
        }


        public int binarySearchFirstColumn(int[][] matrix, int target) {
            int low = -1, high = matrix.length - 1;
            while (low < high) {
                int mid = (high - low + 1) / 2 + low;
                if (matrix[mid][0] <= target) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
            return low;
        }


        public boolean binarySearchRow(int[] row, int target) {
            int low = 0, high = row.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (row[mid] == target) {
                    return true;
                } else if (row[mid] > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return false;
        }
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0){
            return false;
        }
        int row=  findrow(matrix,target);
        if (row> matrix.length-1||row<0){
            return  false;
        }
        return  findcolumn(matrix,target,row);

    }

    public int  findrow(int[][]matrix,int target){
        int lo=0;
        int hi=matrix.length;
        while(lo<=hi){
            int mid=(lo+hi)/2;
//            if(matrix[mid][0]==target){
//                return mid;
//            }else if(matrix[mid][0]>target){
//                hi=mid-1;
//            }else if(matrix[mid][0]<target){
//                lo=mid+1;
//            }
            if (matrix[mid][0]<=target){
                lo=mid;
            }else {
                hi=mid-1;
            }
        }
        return lo;
    }


    public boolean findcolumn(int[][] matrix,int target,int row){
        int[] temp=matrix[row];
        int lo=0;
        int hi=temp.length-1;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            if(temp[mid]==target){
                return true;
            }else if(temp[mid]>target){
                hi=mid-1;
            }else if(temp[mid]<target){
                lo=mid+1;
            }
        }
        return false;
    }


}
